package deom1;

import java.util.HashMap;

public class List {
    static class ListNode {
        public int value;
        public ListNode next;
        ListNode (int value) {
            this.value = value;
        }
    }

    public ListNode re() {
        return head;
    }

    public ListNode partition(ListNode pHead, int x) {
        ListNode max = new ListNode(0);
        ListNode maxV = max;
        ListNode min = new ListNode(0);
        ListNode minV = min;

        ListNode ret = pHead;
        while (ret != null) {
            if (ret.value < x) {
                minV.next = ret;
                minV = ret;
                ret = ret.next;
            } else {
                maxV.next = ret;
                maxV = ret;
                ret = ret.next;
            }
        }
        minV.next = max.next;
        return min.next;
    }

    public ListNode head;

    //长度
    public int size() {
        ListNode ret = head;
        int count = 0;
        while (ret != null) {
            count++;
            ret = ret.next;
        }
        return count;
    }
    //打印
    public void listPrint() {
        ListNode ret = head;
        while (ret != null) {
            System.out.print(ret.value+"  ");
            ret = ret.next;
        }
        System.out.println();
    }

    public void listPrint(ListNode cnt) {
        ListNode ret = cnt;
        while (ret != null) {
            System.out.print(ret.value+"  ");
            ret = ret.next;
        }
        System.out.println();
    }

    //头插
    public void headInsert(int data) {
        ListNode node = new ListNode(data);
        if (head == null) {
            head = node;
        } else {
            node.next = head;
            head = node;
        }
    }

    //尾插
    public void lastInsert(int data) {
        ListNode node = new ListNode(data);
        if(head == null) {
            headInsert(data);
        } else {
            ListNode ret = head;
            while (ret.next != null) {
                ret = ret.next;
            }
            ret.next = node;
        }
    }

    //任意位置插入
    public void posInsert(int pos,int data) {
    ListNode node = new ListNode(data);
    if (pos == 0 || head == null) {
        headInsert(data);
        return;
    }
    if (pos == size()-1) {
        lastInsert(data);
        return;
    }
    if (pos < 0 || pos >= size()) {
        System.out.println("不在范围内！！！");
        return;
    }
    int count = 0;
    ListNode ret = head;
    while (count != pos-1) {
        ret = ret.next;
        count++;
    }
    node.next = ret.next;
    ret.next = node;
    }

    //是否含有
    public boolean contain(int key) {
        if (head == null) {
            return false;
        }
        ListNode ret = head;
        int count = 0;
        while (count != size()) {
            if (ret.value == key) {
                return true;
            }
            count++;
            ret = ret.next;
        }
        return false;
    }

    // 删除数据为 data 的节点
    public void remove(int key) {
        if (head.value == key) {
            head = head.next;
            return;
        }
        ListNode ret = head;
        while (ret.next.value != key) {
            if (ret.next.next == null) {
                System.out.println("没有要删除的值");
                return;
            }
            ret = ret.next;
        }
        ret.next = ret.next.next;
    }

    //删除所有 key 的值
    public void removeAll(int key) {
        while (head.value == key) {
            head = head.next;
        }
        ListNode ret = head;
        while (ret.next != null) {
            int count = 1;
            if (ret.next.value == key) {
                ret.next = ret.next.next;
                count = 0;
            }
            if (count == 1) {
                ret = ret.next;
            }

        }
    }

    //清空
    public void clear() {
        ListNode ret = head;
        while (ret != null) {
            ListNode retV = ret.next;
            ret.next = null;
            ret.value = 0;
            ret = retV;
        }
        head = null;
    }
}

